#define _CRT_SECURE_NO_WARNINGS 1

//#include <iostream>
//using namespace std;
//
//#include <string>
//#include <vector>
//#include <algorithm>

// 快速排序
//void quick_sort(int q[], int l, int r)
//{
//	if (l >= r) return;
//
//	int x = q[(l + r) / 2];
//	int i = l - 1, j = r + 1;
//
//	while (i < j) {
//		do i++; while (q[i] < x);
//		do j--; while (q[j] > x);
//
//		if (i < j) swap(q[i], q[j]);
//	}
//
//	quick_sort(q, l, j);
//	quick_sort(q, j + 1, r);
//}

//int main()
//{
//	int q[] = { 1, 2, 3, 4, 5 };
//	int n = sizeof(q) / sizeof(q[0]);
//
//	quick_sort(q, 0, n - 1);
//
//	for (int e : q) cout << e << " ";
//	cout << endl;
//
//	return 0;
//}

// 归并排序
//const int N = 1e6 + 10;
//int n, q[N], tmp[N];
//
//void merge_sort(int q[], int l, int r)
//{
//    if (l >= r) return;
//
//    int mid = (l + r) >> 1;
//    merge_sort(q, l, mid); merge_sort(q, mid + 1, r);
//
//    int k = 0, i = l, j = mid + 1;
// 
//    while (i <= mid && j <= r) {
//        if (q[i] <= q[j]) tmp[k++] = q[i++];
//        else tmp[k++] = q[j++];
//    }
// 
//    while (i <= mid) tmp[k++] = q[i++];
//    while (j <= r) tmp[k++] = q[j++];
//
//    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//}

//int main()
//{
//    scanf("%d", &n);
//
//    for (int i = 0; i < n; i++) {
//        scanf("%d", &q[i]);
//    }
//
//    merge_sort(q, 0, n - 1);
//
//    for (int i = 0; i < n; i++) {
//        printf("%d ", q[i]);
//    }
//
//    return 0;
//}

// 整数二分
//bool check(int mid) {/*...*/};
//
//int bsearch_1(int l, int r)
//{
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        
//        if (check[mid]) r = mid; // check判断mid是否满足性质
//        else l = mid + 1;
//    }
//
//    return l;
//}
//
//int bsearch_2(int l, int r)
//{
//    while (l < r)
//    {
//        int mid = l + r + 1 >> 1;
//
//        if (check[mid]) l = mid; // check判断mid是否满足性质
//        else r = mid - 1;
//    }
//
//    return l;
//}

// 浮点数二分
//int main()
//{
//    double x;
//    cin >> x;
//
//    double l = 0, r = x;
//    while (r - l > 1e-6) {
//        double mid = (l + r) / 2;
//        if (mid * mid >= x) r = mid;
//        else l = mid;
//    }
//    printf("%lf\n", l);
//
//    return 0;
//}

// 高精度加法
//#include <iostream>
//using namespace std;
//
//#include <vector>
//
//const int N = 1e6 + 10;
//
//vector<int> Add(vector<int>& A, vector<int>& B)
//{
//    int t = 0;
//
//    vector<int> C;
//
//    for (int i = 0; i < A.size() || i < B.size(); i++) {
//        if (i < A.size()) t += A[i];
//        if (i < B.size()) t += B[i];
//
//        C.push_back(t % 10);
//        t /= 10;
//    }
//    if (t) C.push_back(1);
//
//    return C;
//}
//
//int main()
//{
//    string a, b;
//    cin >> a >> b;
//
//    vector<int> A, B;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
//
//    auto C = Add(A, B);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//
//    return 0;
//}

// 高精度减法
//#include <iostream>
//using namespace std;
//
//#include <vector>
//#include <string>
//
//// 判断是否 A >= B
//bool cmp(vector<int>& A, vector<int>& B)
//{
//    if (A.size() != B.size()) {
//        return A.size() > B.size();
//    }
//    else {
//        for (int i = A.size() - 1; i >= 0; i--)
//            if (A[i] != B[i])
//                return A[i] > B[i];
//    }
//
//    return true;
//}
//
//vector<int> Sub(vector<int>& A, vector<int>& B)
//{
//    int t = 0;
//
//    vector<int> C;
//
//    for (int i = 0; i < A.size(); i++) {
//        t = A[i] - t;
//
//        if (i < B.size()) t -= B[i];
//
//        C.push_back((t + 10) % 10);
//
//        if (t < 0) t = 1;
//        else t = 0;
//    }
//
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a, b;
//    cin >> a >> b;
//
//    vector<int> A, B;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
//
//    if (cmp(A, B)) {
//        auto C = Sub(A, B);
//        for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    }
//    else {
//        cout << "-";
//        auto C = Sub(B, A);
//        for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    }
//
//
//    return 0;
//}

// 高精度乘法
//#include <iostream>
//using namespace std;
//
//#include <vector>
//#include <string>
//
//vector<int> Mul(vector<int>& A, int b)
//{
//    int t = 0;
//    vector<int> C;
//
//    for (int i = 0; i < A.size() || t; i++) {
//        if (i < A.size()) t += A[i] * b;
//        C.push_back(t % 10);
//        t /= 10;
//    }
//
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a;
//    int b;
//
//    cin >> a >> b;
//
//    vector<int> A;
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//
//    auto C = Mul(A, b);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//
//    return 0;
//}

// 高精度除法
//#include <iostream>
//using namespace std;
//
//#include <string>
//#include <vector>
//#include <algorithm>
//
//vector<int> Div(vector<int>& A, int b, int& r)
//{
//    r = 0;
//    vector<int> C;
//
//    for (int i = A.size() - 1; i >= 0; i--) {
//        r = r * 10 + A[i];
//        C.push_back(r / b);
//        r %= b;
//    }
//    reverse(C.begin(), C.end());
//
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a;
//    int b;
//
//    cin >> a >> b;
//
//    vector<int> A;
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//
//    int r;
//    auto C = Div(A, b, r);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    cout << endl << r;
//
//    return 0;
//}

// 一维前缀和
//#include <iostream>
//using namespace std;
//
//const int N = 1e5 + 10;
//int a[N], s[N];
//int n, m;
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//
//    for (int i = 1; i <= n; i++)
//    {
//        scanf("%d", &a[i]);
//        s[i] = s[i - 1] + a[i];
//    }
//
//    while (m--) {
//        int l, r;
//        scanf("%d %d", &l, &r);
//
//        printf("%d\n", s[r] - s[l - 1]);
//
//    }
//
//    return 0;
//}

// 二维前缀和
//#include <iostream>
//using namespace std;
//
//int n, m, q;
//const int N = 1e3 + 10;
//int a[N][N], s[N][N];
//
//int main()
//{
//    scanf("%d %d %d", &n, &m, &q);
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            scanf("%d", &a[i][j]);
//
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
//        }
//
//
//    while (q--) {
//        int x1, x2, y1, y2;
//        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
//        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
//
//    }
//
//    return 0;
//}

// 一维差分
//#include <iostream>
//using namespace std;
//
//int n, m;
//const int N = 1e5 + 10;
//int a[N], b[N];
//
//void insert(int l, int r, int c)
//{
//    b[l] += c;
//    b[r + 1] -= c;
//}
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//
//    for (int i = 1; i <= n; i++) {
//        scanf("%d", &a[i]);
//        insert(i, i, a[i]);
//    }
//
//    while (m--) {
//        int l, r, c;
//        scanf("%d %d %d", &l, &r, &c);
//        insert(l, r, c);
//    }
//
//    for (int i = 1; i <= n; i++) {
//        b[i] += b[i - 1];
//        printf("%d ", b[i]);
//    }
//
//    return 0;
//}

// 二维差分
//#include <iostream>
//using namespace std;
//
//int n, m, q;
//const int N = 1e3 + 10;
//int a[N][N], b[N][N];
//
//void insert(int x1, int y1, int x2, int y2, int c)
//{
//    b[x1][y1] += c;
//    b[x2 + 1][y2 + 1] += c;
//    b[x1][y2 + 1] -= c;
//    b[x2 + 1][y1] -= c;
//}
//
//int main()
//{
//    scanf("%d %d %d", &n, &m, &q);
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++) {
//            scanf("%d", &a[i][j]);
//            insert(i, j, i, j, a[i][j]);
//        }
//
//    while (q--) {
//        int x1, y1, x2, y2, c;
//        cin >> x1 >> y1 >> x2 >> y2 >> c;
//        insert(x1, y1, x2, y2, c);
//    }
//
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= m; j++) {
//            b[i][j] = b[i][j] + b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1];
//            printf("%d ", b[i][j]);
//        }
//        putchar('\n');
//    }
//
//    return 0;
//}

// 快速选择算法
//const int N = 1e5 + 10;
//
//int n, k;
//int q[N];
//
//int quick_sort(int l, int r, int k)
//{
//	if (l >= r) return q[r];
//
//	int x = q[(l + r) / 2];
//	int i = l - 1, j = r + 1;
//	while (i < j) {
//		do i++; while (q[i] < x);
//		do j--; while (q[j] > x);
//
//		if (i < j) swap(q[i], q[j]);
//	}
//
//	int sl = j - l + 1;
//	if (k <= sl) return quick_sort(l, j, k);
//
//	return quick_sort(j + 1, r, k - sl);
//}
//
//int main()
//{
//	cin >> n >> k;
//
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	cout << quick_sort(0, n - 1, k) << endl;
//
//	return 0;
//}

// 双指针
//#include <iostream>
//using namespace std;
//
//int n;
//
//const int N = 1e5 + 10;
//int a[N], s[N];
//
//int main()
//{
//    scanf("%d", &n);
//
//    for (int i = 0; i < n; i++) cin >> a[i];
//
//    int res = 0;
//    for (int i = 0, j = 0; i < n; i++) {
//        s[a[i]]++;
//
//        while (s[a[i]] > 1) {
//            s[a[j]]--;
//            j++;
//        }
//        res = max(res, i - j + 1);
//    }
//
//    cout << res << endl;
//
//    return 0;
//}

// 位运算
//求n的第k位数字: n >> k & 1
//返回n的最后一位1：lowbit(n) = n & -n

// 二进制中1的个数
//#include <iostream>
//using namespace std;
//
//const int N = 1e5 + 10;
//
//int n, a[N];
//
//int lowbit(int x)
//{
//    return x & -x;
//}
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//
//        int res = 0;
//        while (a[i]) {
//            res += 1;
//            a[i] -= lowbit(a[i]);
//        }
//
//        cout << res << " ";
//    }
//
//    return 0;
//}

// 离散化
//vector<int> alls; // 存储所有待离散化的值
//sort(alls.begin(), alls.end()); // 将所有值排序
//alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
//
//// 二分求出x对应的离散化的值
//int find(int x) // 找到第一个大于等于x的位置
//{
//    int l = 0, r = alls.size() - 1;
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        if (alls[mid] >= x) r = mid;
//        else l = mid + 1;
//    }
//    return r + 1; // 映射到1, 2, ...n
//}

// 区间合并
//void merge(vector<PII>& segs)
//{
//    vector<PII> res;
//
//    sort(segs.begin(), segs.end());
//
//    int st = -2e9, ed = -2e9;
//    for (auto seg : segs)
//        if (ed < seg.first)
//        {
//            if (st != -2e9) res.push_back({ st, ed });
//            st = seg.first, ed = seg.second;
//        }
//        else ed = max(ed, seg.second);
//
//    if (st != -2e9) res.push_back({ st, ed });
//
//    segs = res;
//}

//#include <iostream>
//using namespace std;

// 静态链表
//int m;
//
//const int N = 1e5 + 10;
//int e[N], ne[N], head, idx;
//
//void init()
//{
//    head = -1;
//    idx = 0;
//}
//
//void add_to_head(int x)
//{
//    e[idx] = x;
//    ne[idx] = head;
//    head = idx;
//    idx++;
//}
//
//void add(int k, int x)
//{
//    e[idx] = x;
//    ne[idx] = ne[k];
//    ne[k] = idx;
//    idx++;
//}
//
//void remove(int k)
//{
//    ne[k] = ne[ne[k]];
//}
//
//int main()
//{
//    cin >> m;
//
//    while (m--)
//    {
//        char op;
//        cin >> op;
//
//        if (op == 'H') {
//            int x;
//            cin >> x;
//            add_to_head(x);
//        }
//        else if (op == 'I') {
//            int k, x;
//            cin >> k >> x;
//            add(k - 1, x);
//        }
//        else {
//            int k;
//            cin >> k;
//
//            if (!k) head = ne[head];
//            else remove(k - 1);
//        }
//    }
//
//    for (int i = head; i != -1; i = ne[i]) cout << e[i];
//    cout << endl;
//
//    return 0;
//}

// 双链表
//#include <iostream>
//using namespace std;
//#include <string>
//
//int m;
//
//const int N = 1e5 + 10;
//int e[N], l[N], r[N], idx;
//
//void init()
//{
//    r[0] = 1, l[1] = 0;
//    idx = 2;
//}
//
//// 在下标为k的后面插入一个数
//void insert(int k, int x)
//{
//    e[idx] = x;
//    l[idx] = k;
//    r[idx] = r[k];
//
//    l[r[k]] = idx;
//    r[k] = idx;
//
//    idx++;
//}
//
//void remove(int k)
//{
//    r[l[k]] = r[k];
//    l[r[k]] = l[k];
//}
//
//int main()
//{
//    cin >> m;
//
//    init();
//
//    while (m--)
//    {
//        string op;
//        cin >> op;
//
//        if (op == "L") {
//            int x; cin >> x;
//            insert(0, x);
//        }
//        else if (op == "R") {
//            int x; cin >> x;
//            insert(l[1], x);
//        }
//        else if (op == "D") {
//            int k; cin >> k;
//            remove(k + 1);
//        }
//        else if (op == "IL") {
//            int k, x;
//            cin >> k >> x;
//            insert(l[k + 1], x);
//        }
//        else {
//            int k, x;
//            cin >> k >> x;
//            insert(k + 1, x);
//        }
//    }
//
//    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
//    cout << endl;
//
//    return 0;
//}

// 模拟栈
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//
//int m;
//int stk[N], tt;
//
//int main()
//{
//    cin >> m;
//    while (m--)
//    {
//        string op;
//        int x;
//
//        cin >> op;
//        if (op == "push")
//        {
//            cin >> x;
//            stk[++tt] = x;
//        }
//        else if (op == "pop") tt--;
//        else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
//        else cout << stk[tt] << endl;
//    }
//
//    return 0;
//}

// 模拟队列
//#include <iostream>
//using namespace std;
//
//int m;
//const int N = 1e5 + 10;
//
//int q[N], hh, tt = -1;
//
//void push(int x)
//{
//    q[++tt] = x;
//}
//
//void pop()
//{
//    ++hh;
//}
//
//bool empty()
//{
//    return hh > tt;
//}
//
//int query()
//{
//    return q[hh];
//}
//
//int main()
//{
//    cin >> m;
//
//    while (m--) {
//        string op;
//        cin >> op;
//
//        if (op == "push") {
//            int x; cin >> x;
//            push(x);
//        }
//        else if (op == "pop") {
//            pop();
//        }
//        else if (op == "empty") {
//            if (empty()) cout << "YES" << endl;
//            else cout << "NO" << endl;
//        }
//        else {
//            cout << query() << endl;
//        }
//    }
//
//    return 0;
//}

// 单调栈
//int n;
//
//const int N = 1e5 + 10;
//int stk[N], tt;
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 0; i < n; i++) {
//        int x; cin >> x;
//        while (tt && stk[tt] >= x) --tt;
//
//        if (!tt) cout << -1 << " ";
//        else cout << stk[tt] << " ";
//
//        stk[++tt] = x;
//    }
//
//    return 0;
//}

// 单调队列
//#include <iostream>
//using namespace std;
//
//int n, k;
//
//const int N = 1e6 + 10;
//int a[N], q[N];
//
//int main()
//{
//    scanf("%d %d", &n, &k);
//
//    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
//
//    int hh = 0, tt = -1;
//    for (int i = 0; i < n; i++) {
//        if (hh <= tt && i - k + 1 > q[hh]) ++hh;
//        while (hh <= tt && a[q[tt]] >= a[i]) --tt;
//        q[++tt] = i;
//        if (i + 1 >= k) cout << a[q[hh]] << " ";
//    }
//    cout << endl;
//
//    hh = 0, tt = -1;
//    for (int i = 0; i < n; i++) {
//        if (hh <= tt && i - k + 1 > q[hh]) ++hh;
//        while (hh <= tt && a[q[tt]] <= a[i]) --tt;
//        q[++tt] = i;
//        if (i + 1 >= k) cout << a[q[hh]] << " ";
//    }
//    cout << endl;
//
//
//    return 0;
//}

// KMP(STL版本)
//int KMP(string main, string pattern)
//{
//	string s = pattern + "#" + main;
//	vector<int> pi(s.size());
//
//	for (int i = 1; i < s.size(); i++) {
//		int len = pi[i - 1];
//
//		while (len != 0 && s[i] != s[len]) {
//			len = pi[len - 1];
//		}
//
//		if (s[i] == s[len]) {
//			pi[i] = len + 1;
//			if (pi[i] == pattern.size()) {
//				return i - 2 * pattern.size();
//			}
//		}
//
//	}
//
//	return -1;
//}
//
//int main()
//{
//	string main, pattern;
//	cin >> main >> pattern;
//
//	cout << KMP(main, pattern) << endl;
//
//	return 0;
//}

// KMP(静态数组版本)
//#include <iostream>
//using namespace std;
//
//int n, m;
//
//const int N = 1e5 + 10, M = 1e6 + 10;
//
//char p[N], s[M];
//int ne[N];
//
//int main()
//{
//	cin >> n >> p + 1 >> m >> s + 1;
//
//	for (int i = 2, j = 0; i <= n; i++) {
//		while (j && p[i] != p[j + 1]) j = ne[j];
//		if (p[i] == p[j + 1]) j++;
//		ne[i] = j;
//	}
//
//	for (int i = 1, j = 0; i <= m; i++) {
//		while (j && s[i] != p[j + 1]) j = ne[j];
//		if (s[i] == p[j + 1]) j++;
//		if (j == n) {
//			printf("%d ", i - n);
//			j = ne[j];
//		}
//	}
//
//	return 0;
//}

// 字符串统计
//int son[N][26], cnt[N], idx;
//// 0号点既是根节点，又是空节点
//// son[][]存储树中每个节点的子节点
//// cnt[]存储以每个节点结尾的单词数量
//
//// 插入一个字符串
//void insert(char* str)
//{
//    int p = 0;
//    for (int i = 0; str[i]; i++)
//    {
//        int u = str[i] - 'a';
//        if (!son[p][u]) son[p][u] = ++idx;
//        p = son[p][u];
//    }
//    cnt[p]++;
//}
//
//// 查询字符串出现的次数
//int query(char* str)
//{
//    int p = 0;
//    for (int i = 0; str[i]; i++)
//    {
//        int u = str[i] - 'a';
//        if (!son[p][u]) return 0;
//        p = son[p][u];
//    }
//    return cnt[p];
//}

// 并查集
//#include <iostream>
//using namespace std;
//
//const int N = 1e5 + 10;
//int p[N], n, m;
//
//int find(int x)
//{
//    if (p[x] != x) p[x] = find(p[x]);
//    return p[x];
//}
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//
//    for (int i = 1; i <= n; i++) p[i] = i;
//
//    while (m--) {
//        char op[2];
//        int a, b;
//        scanf("%s %d %d", op, &a, &b);
//
//        if (op[0] == 'M') {
//            p[find(a)] = find(b);
//        }
//        else {
//            if (find(a) == find(b)) puts("Yes");
//            else puts("No");
//        }
//    }
//
//    return 0;
//}

// 并查集 （维护size版本）
//#include <iostream>
//using namespace std;
//
//const int N = 1e5 + 10;
//int p[N], se[N];
//int n, m;
//
//int find(int x)
//{
//    if (p[x] != x) p[x] = find(p[x]);
//    return p[x];
//}
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//
//    for (int i = 1; i <= n; i++) {
//        p[i] = i;
//        se[i] = 1;
//    }
//
//    while (m--) {
//        char op[5];
//        int a, b;
//        scanf("%s", op);
//
//        if (op[0] == 'C') {
//            scanf("%d %d", &a, &b);
//            if (find(a) != find(b)) se[find(b)] += se[find(a)];
//            p[find(a)] = find(b);
//        }
//        else if (op[1] == '1') {
//            scanf("%d %d", &a, &b);
//            if (find(a) == find(b)) puts("Yes");
//            else puts("No");
//        }
//        else {
//            scanf("%d", &a);
//            printf("%d\n", se[find(a)]);
//        }
//    }
//
//    return 0;
//}

// 堆排序 (向下调整)
//#include <iostream>
//using namespace std;
//
//#include <algorithm>
//
//const int N = 1e5 + 10;
//int h[N];
//int n, m, se;
//
//void down(int u)
//{
//    int t = u;
//    if (u * 2 <= se && h[u * 2] < h[t]) t = u * 2;
//    if (u * 2 + 1 <= se && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
//    if (t != u) {
//        swap(h[t], h[u]);
//        down(t);
//    }
//}
// 
//void up(int u)
//{
//	while (u / 2 && h[u] < h[u / 2]) {
//		swap(h[u], h[u / 2]);
//		u >>= 1;
//	}
//}
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//    se = n;
//
//    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
//
//    for (int i = n / 2; i >= 0; i--) down(i);
//
//    while (m--) {
//        printf("%d ", h[1]);
//        h[1] = h[se];
//        se--;
//        down(1);
//    }
//
//    return 0;
//}

// 模拟堆
// 
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
// 
// int h[N], ph[N], hp[N], size;
//
//// 交换两个点，及其映射关系
// void heap_swap(int a, int b)
// {
//    swap(ph[hp[a]], ph[hp[b]]);
//    swap(hp[a], hp[b]);
//    swap(h[a], h[b]);
// }
//
//void down(int u)
//{
//    int t = u;
//    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
//    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
//    if (u != t)
//    {
//        heap_swap(u, t);
//        down(t);
//    }
//}
//
//void up(int u)
//{
//    while (u / 2 && h[u] < h[u / 2])
//    {
//        heap_swap(u, u / 2);
//        u >>= 1;
//    }
//}
//
//// O(n)建堆
//for (int i = n / 2; i; i--) down(i);

// 模拟散列表 (拉链法)
//#include <iostream>
//#include <cstring>
//
//using namespace std;
//
//const int N = 1e5 + 3;
//
//int h[N], e[N], ne[N];
//int n, idx;
//
//void insert(int x)
//{
//    int k = (x % N + N) % N;
//    e[idx] = x;
//    ne[idx] = h[k];
//    h[k] = idx;
//    idx++;
//}
//
//bool find(int x)
//{
//    int k = (x % N + N) % N;
//    for (int i = h[k]; i != -1; i = ne[i])
//        if (e[i] == x)
//            return true;
//
//    return false;
//}
//
//int main()
//{
//    scanf("%d", &n);
//
//    memset(h, -1, sizeof h);
//
//    while (n--) {
//        char op[2]; int x;
//        scanf("%s %d", op, &x);
//
//        if (op[0] == 'I')   insert(x);
//        else {
//            if (find(x)) puts("Yes");
//            else puts("No");
//        }
//    }
//
//    return 0;
//}

// 中缀表达式
//#include <iostream>
//using namespace std;
//
//#include <stack>
//#include <cstring>
//#include <unordered_map>
//
//stack<int> num;
//stack<char> op;
//
//void eval()
//{
//    int b = num.top(); num.pop();
//    int a = num.top(); num.pop();
//    char c = op.top(); op.pop();
//
//    int x;
//
//    if (c == '+') x = a + b;
//    else if (c == '-') x = a - b;
//    else if (c == '*') x = a * b;
//    else x = a / b;
//
//    num.push(x);
//}
//
//int main()
//{
//    string str;
//    cin >> str;
//
//    unordered_map<char, int> pr = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };
//
//    for (int i = 0; i < str.size(); i++) {
//        char c = str[i];
//
//        if (isdigit(c)) {
//            int x = 0, j = i;
//            while (j < str.size() && isdigit(str[j])) {
//                x = x * 10 + str[j] - '0';
//                j++;
//            }
//            i = j - 1;
//            num.push(x);
//        }
//
//        else if (c == '(') op.push('(');
//
//        else if (c == ')') {
//            while (op.top() != '(') eval();
//            op.pop();
//        }
//
//        else {
//            while (op.size() && pr[str[i]] <= pr[op.top()]) eval();
//            op.push(c);
//        }
//
//    }
//
//    while (op.size()) eval();
//    cout << num.top() << endl;
//
//
//    return 0;
//}

// 开放寻址法
// 只开了一个一维数组
// 但是一维数组的长度从经验上来说是题目数据范围的2 ~ 3倍
//int h[N];
//
//// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
//int find(int x)
//{
//    int t = (x % N + N) % N;
//    while (h[t] != null && h[t] != x)
//    {
//        t++;
//        if (t == N) t = 0;
//    }
//    return t;
//}

// 并查集（维护到祖宗节点的距离）
//#include <iostream>
//using namespace std;
//
//const int N = 5e4 + 10;
//
//int n, m;
//int p[N], d[N];
//
//int find(int x)
//{
//    if (p[x] != x)
//    {
//        int t = find(p[x]);
//        d[x] += d[p[x]];
//        p[x] = t;
//    }
//    return p[x];
//}
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//
//    for (int i = 1; i <= n; i++) p[i] = i;
//
//    int res = 0;
//    while (m--)
//    {
//        int t, x, y;
//        scanf("%d %d %d", &t, &x, &y);
//
//        if (x > n || y > n) res++;
//        else {
//            int px = find(x), py = find(y);
//
//            if (t == 1) {
//                if (px == py && (d[x] - d[y]) % 3) res++;
//                else if (px != py) {
//                    p[px] = py;
//                    d[px] = d[y] - d[x];
//                }
//            }
//
//            else if (t == 2) {
//                if (px == py && (d[x] - d[y] - 1) % 3) res++;
//                else if (px != py) {
//                    p[px] = py;
//                    d[px] = d[y] - d[x] + 1;
//                }
//            }
//        }
//    }
//
//    printf("%d", res);
//
//    return 0;
//}

// 质数的判断
// 因数必定成对出现
//bool is_prime(int n)
//{
//    if (n < 2) return false;
//    for (int i = 2; i <= n / i; i++)
//        if (n % i == 0)
//            return false;
//    return true;
//}

// 分解质因数
// 一个数x，最多只有一个大于sqrt(x)的质因数
//void divide(int x)
//{
//    for (int i = 2; i <= x / i; i++)
//        if (x % i == 0)
//        {
//            int s = 0;
//            while (x % i == 0) x /= i, s++;
//            cout << i << ' ' << s << endl;
//        }
//    if (x > 1) cout << x << ' ' << 1 << endl;
//    cout << endl;
//}

// 朴素筛质数法
//int primes[N], cnt;     // primes[]存储所有素数
//bool st[N];         // st[x]存储x是否被筛掉
//
//void get_primes(int n)
//{
//    for (int i = 2; i <= n; i++)
//    {
//        if (st[i]) continue;
//        primes[cnt++] = i;
//        for (int j = i + i; j <= n; j += i)
//            st[j] = true;
//    }
//}

// 线性筛选质数法
// 用最小质因子来筛，每个数又只有一个最小质因子
// 因此是线性的
//int primes[N], cnt;     // primes[]存储所有素数
//bool st[N];         // st[x]存储x是否被筛掉
//
//void get_primes(int n)
//{
//    for (int i = 2; i <= n; i++)
//    {
//        if (!st[i]) primes[cnt++] = i;
//        for (int j = 0; primes[j] <= n / i; j++)
//        {
//            st[primes[j] * i] = true;
//            if (i % primes[j] == 0) break;
//        }
//    }
//}

// 试除法求约数
//vector<int> get_divisors(int x)
//{
//    vector<int> res;
//    for (int i = 1; i <= x / i; i++)
//        if (x % i == 0)
//        {
//            res.push_back(i);
//            if (i != x / i) res.push_back(x / i);
//        }
//    sort(res.begin(), res.end());
//    return res;
//}

// 约数个数 和 约数之和
// 如果 N = p1 ^ c1 * p2 ^ c2 * ... *pk ^ ck
// 约数个数：(c1 + 1) * (c2 + 1) * ... * (ck + 1)
// 约数之和：(p1 ^ 0 + p1 ^ 1 + ... + p1 ^ c1) * ... * (pk ^ 0 + pk ^ 1 + ... + pk ^ ck)

// 最大公约数
//int gcd(int a, int b)
//{
//    return b ? gcd(b, a % b) : a;
//}

// 求欧拉公式
//int phi(int x)
//{
//    int res = x;
//    for (int i = 2; i <= x / i; i++)
//        if (x % i == 0)
//        {
//            res = res / i * (i - 1);
//            while (x % i == 0) x /= i;
//        }
//    if (x > 1) res = res / x * (x - 1);
//
//    return res;
//}

// 筛选求欧拉函数
//int primes[N], cnt;     // primes[]存储所有素数
//int euler[N];           // 存储每个数的欧拉函数
//bool st[N];             // st[x]存储x是否被筛掉
//
//void get_eulers(int n)
//{
//    euler[1] = 1;
//    for (int i = 2; i <= n; i++)
//    {
//        if (!st[i])
//        {
//            primes[cnt++] = i;
//            euler[i] = i - 1;
//        }
//        for (int j = 0; primes[j] <= n / i; j++)
//        {
//            int t = primes[j] * i;
//            st[t] = true;
//            if (i % primes[j] == 0)
//            {
//                euler[t] = euler[i] * primes[j];
//                break;
//            }
//            euler[t] = euler[i] * (primes[j] - 1);
//        }
//    }
//}

// 快速幂
//求 m^ k mod p，时间复杂度 O(logk)。
//
//int qmi(int m, int k, int p)
//{
//    int res = 1 % p, t = m;
//    while (k)
//    {
//        if (k & 1) res = res * t % p;
//        t = t * t % p;
//        k >>= 1;
//    }
//    return res;
//}

// 邻接表
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
//int h[N], e[N], ne[N], idx;
//
//// 添加一条边a->b
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//
//// 初始化
//idx = 0;
//memset(h, -1, sizeof h);

// 字符串哈希
//#include <iostream>
//using namespace std;
//
//typedef unsigned long long ULL;
//
//const int N = 1e5 + 10, P = 131;
//int n, m;
//
//ULL h[N], p[N];
//char str[N];
//
//ULL get(int l, int r)
//{
//    return h[r] - h[l - 1] * p[r - l + 1];
//}
//
//int main()
//{
//    scanf("%d %d %s", &n, &m, str + 1);
//
//    p[0] = 1;
//    for (int i = 1; i <= n; i++) {
//        p[i] = p[i - 1] * P;
//        h[i] = h[i - 1] * P + str[i];
//    }
//
//    while (m--)
//    {
//        int l1, r1, l2, r2;
//        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
//
//        if (get(l1, r1) == get(l2, r2)) puts("Yes");
//        else puts("No");
//    }
//
//
//    return 0;
//}

// dfs
//void dfs(int u)
//{
// 
//    st[u] = true; // st[u] 表示点u已经被遍历过
//
//    for (int i = h[u]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        if (!st[j]) dfs(j);
//    }
// 
//}

// 树是连通无向图，若有向则最多只有 n - 1 条边
// dfs实例
//#include <cstdio>
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 100010, M = N * 2;
//
//int n;
//int h[N], e[M], ne[M], idx;
//int ans = N;
//bool st[N];
//
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//
//int dfs(int u)
//{
//    st[u] = true;
//
//    int size = 0, sum = 0;
//    for (int i = h[u]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        if (st[j]) continue;
//
//        int s = dfs(j);
//        size = max(size, s);
//        sum += s;
//    }
//
//    size = max(size, n - sum - 1);
//    ans = min(ans, size);
//
//    return sum + 1;
//}
//
//int main()
//{
//    scanf("%d", &n);
//
//    memset(h, -1, sizeof h);
//
//    for (int i = 0; i < n - 1; i++)
//    {
//        int a, b;
//        scanf("%d%d", &a, &b);
//        add(a, b), add(b, a);
//    }
//
//    dfs(1);
//
//    printf("%d\n", ans);
//
//    return 0;
//}

// bfs
//queue<int> q;
//st[1] = true; // 表示1号点已经被遍历过
//q.push(1);
//
//while (q.size())
//{
//    int t = q.front();
//    q.pop();
//
//    for (int i = h[t]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        if (!st[j])
//        {
//            st[j] = true; // 表示点j已经被遍历过
//            q.push(j);
//        }
//    }
//}

// 拓扑排序
// 用来解决有向无环图的场景
//bool topsort()
//{
//    int hh = 0, tt = -1;
//
//    // d[i] 存储点i的入度
//    for (int i = 1; i <= n; i++)
//        if (!d[i])
//            q[++tt] = i;
//
//    while (hh <= tt)
//    {
//        int t = q[hh++];
//
//        for (int i = h[t]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (--d[j] == 0)
//                q[++tt] = j;
//        }
//    }
//
//    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
//    return tt == n - 1;
//}

// 朴素dijkstra算法
// 时间复杂是 O(n^2 + m) n表示点数，𝑚表示边数
//int g[N][N];  // 存储每条边
//int dist[N];  // 存储1号点到每个点的最短距离
//bool st[N];   // 存储每个点的最短路是否已经确定
//
//// 求1号点到n号点的最短路，如果不存在则返回-1
//int dijkstra()
//{
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
//
//    for (int i = 0; i < n - 1; i++)
//    {
//        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
//        for (int j = 1; j <= n; j++)
//            if (!st[j] && (t == -1 || dist[t] > dist[j]))
//                t = j;
//
//        // 用t更新其他点的距离
//        for (int j = 1; j <= n; j++)
//            dist[j] = min(dist[j], dist[t] + g[t][j]);
//
//        st[t] = true;
//    }
//
//    if (dist[n] == 0x3f3f3f3f) return -1;
//    return dist[n];
//}

// 堆优化dijkstra算法
// 时间复杂度 O(mlogn)𝑛表示点数，𝑚表示边数
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//#include <queue>
//
//using namespace std;
//
//typedef pair<int, int> PII;
//
//const int N = 1e6 + 10;
//
//int n, m;
//int h[N], w[N], e[N], ne[N], idx;
//int dist[N];
//bool st[N];
//
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//
//int dijkstra()
//{
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
//    priority_queue<PII, vector<PII>, greater<PII>> heap;
//    heap.push({ 0, 1 });
//
//    while (heap.size())
//    {
//        auto t = heap.top();
//        heap.pop();
//
//        int ver = t.second, distance = t.first;
//
//        if (st[ver]) continue;
//        st[ver] = true;
//
//        for (int i = h[ver]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dist[j] > dist[ver] + w[i])
//            {
//                dist[j] = dist[ver] + w[i];
//                heap.push({ dist[j], j });
//            }
//        }
//    }
//
//    if (dist[n] == 0x3f3f3f3f) return -1;
//    return dist[n];
//}
//
//int main()
//{
//    scanf("%d%d", &n, &m);
//
//    memset(h, -1, sizeof h);
//    while (m--)
//    {
//        int a, b, c;
//        scanf("%d%d%d", &a, &b, &c);
//        add(a, b, c);
//    }
//
//    printf("%d\n", dijkstra());
//
//    return 0;
//}

// 01背包
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 1010;
//int n, m;
//int v[N], w[N];
//int f[N][N];
//
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 0; j <= m; j++)
//        {
//            f[i][j] = f[i - 1][j];
//            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
//        }
//
//    cout << f[n][m] << endl;
//
//    return 0;
//}

// 01背包(一维)
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 1010;
//int n, m;
//int v[N], w[N], f[N];
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = m; j >= v[i]; j--)
//        {
//            f[j] = max(f[j], f[j - v[i]] + w[i]);
//        }
//
//    cout << f[m] << endl;
//
//    return 0;
//}

// 完全背包问题
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 1010;
//int n, m;
//int v[N], w[N];
//int f[N][N];
//
//int main()
//{
//    cin >> n >> m;
//
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 0; j <= m; j++)
//        {
//            f[i][j] = f[i - 1][j];
//            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
//        }
//
//    cout << f[n][m] << endl;
//
//    return 0;
//}

// 多重背包
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 110;
//int n, m;
//int v[N], w[N], s[N];
//int f[N][N];
//
//int main()
//{
//    cin >> n >> m;
//
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 0; j <= m; j++)
//            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
//                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
//
//    cout << f[n][m] << endl;
//
//    return 0;
//}

// 多重背包(二进制优化)
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 25000;
//int n, m;
//int v[N], w[N];
//int f[N];
//
//int main()
//{
//    cin >> n >> m;
//
//    int cnt = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//
//        int k = 1;
//
//        while (k <= c)
//        {
//            cnt++;
//            v[cnt] = a * k;
//            w[cnt] = b * k;
//            c -= k;
//            k *= 2;
//        }
//
//        if (c > 0)
//        {
//            cnt++;
//            v[cnt] = a * c;
//            w[cnt] = b * c;
//        }
//    }
//
//    n = cnt;
//
//    for (int i = 1; i <= n; i++)
//        for (int j = m; j >= v[i]; j--)
//            f[j] = max(f[j], f[j - v[i]] + w[i]);
//
//    cout << f[m] << endl;
//
//    return 0;
//}

// 分组背包问题
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 110;
//int n, m;
//int v[N][N], w[N][N], s[N];
//int f[N];
//
//int main()
//{
//    cin >> n >> m;
//
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> s[i];
//        for (int j = 0; j < s[i]; j++)
//        {
//            cin >> v[i][j] >> w[i][j];
//        }
//    }
//
//    for (int i = 1; i <= n; i++)
//        for (int j = m; j >= 0; j--)
//            for (int k = 0; k < s[i]; k++)
//            {
//                if (j - v[i][k] >= 0)
//                {
//                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
//                }
//            }
//
//    cout << f[m] << endl;
//
//    return 0;
//}

// 线性DP
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 510, INF = -1e8;
//int n;
//int a[N][N];
//int f[N][N];
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= i; j++)
//            cin >> a[i][j];
//
//    for (int i = 0; i <= n; i++)
//        for (int j = 0; j <= i + 1; j++)
//            f[i][j] = INF;
//
//    f[1][1] = a[1][1];
//
//    for (int i = 2; i <= n; i++)
//        for (int j = 1; j <= i; j++)
//            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
//
//    int ret = INF;
//
//    for (int i = 1; i <= n; i++) ret = max(ret, f[n][i]);
//    cout << ret << endl;
//
//    return 0;
//}

// 区间dp
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 310;
//int n;
//int s[N];
//int f[N][N];
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> s[i];
//        s[i] += s[i - 1];
//    }
//
//    for (int len = 2; len <= n; len++)
//    {
//        for (int i = 1; i + len - 1 <= n; i++)
//        {
//            int l = i, r = i + len - 1;
//
//            f[l][r] = 1e9;
//            for (int k = l; k < r; k++)
//            {
//                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
//            }
//        }
//    }
//
//    cout << f[1][n] << endl;
//
//    return 0;
//}

// 计数类dp
//#include <iostream>
//using namespace std;
//
//const int N = 1010, mod = 1e9 + 7;
//
//int n;
//int f[N][N];
//
//int main()
//{
//    scanf("%d", &n);
//
//    f[0][0] = 1;
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= i; j++)
//            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
//
//    int res = 0;
//    for (int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
//
//    printf("%d", res);
//
//    return 0;
//}

// bellman_ford
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 510, M = 10010;
//int n, m, k;
//int dist[N], backup[N];
//bool check = true;
//
//struct Edge
//{
//    int a, b, w;
//}edges[M];
//
//bool bellman_ford()
//{
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
//
//    for (int i = 0; i < k; i++)
//    {
//        memcpy(backup, dist, sizeof dist);
//
//        for (int j = 0; j < m; j++)
//        {
//            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
//            dist[b] = min(dist[b], backup[a] + w);
//        }
//    }
//
//    if (dist[n] > 0x3f3f3f3f / 2) check = false;
//    return check;
//}
//
//int main()
//{
//    scanf("%d %d %d", &n, &m, &k);
//
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, w;
//        scanf("%d %d %d", &a, &b, &w);
//        edges[i] = { a, b, w };
//    }
//
//    bool t = bellman_ford();
//
//    if (t == false) puts("impossible");
//    else printf("%d\n", dist[n]);
//
//    return 0;
//}

// spfa求最短路
//int n;      // 总点数
//int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
//int dist[N];        // 存储每个点到1号点的最短距离
//bool st[N];     // 存储每个点是否在队列中
//
//// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
//int spfa()
//{
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
//
//    queue<int> q;
//    q.push(1);
//    st[1] = true;
//
//    while (q.size())
//    {
//        auto t = q.front();
//        q.pop();
//
//        st[t] = false;
//
//        for (int i = h[t]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dist[j] > dist[t] + w[i])
//            {
//                dist[j] = dist[t] + w[i];
//                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
//                {
//                    q.push(j);
//                    st[j] = true;
//                }
//            }
//        }
//    }
//
//    if (dist[n] == 0x3f3f3f3f) return -1;
//    return dist[n];
//}

// spfa判断负环
//int n;      // 总点数
//int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
//int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
//bool st[N];     // 存储每个点是否在队列中
//
//// 如果存在负环，则返回true，否则返回false。
//bool spfa()
//{
//    // 不需要初始化dist数组
//    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
//
//    queue<int> q;
//    for (int i = 1; i <= n; i++)
//    {
//        q.push(i);
//        st[i] = true;
//    }
//
//    while (q.size())
//    {
//        auto t = q.front();
//        q.pop();
//
//        st[t] = false;
//
//        for (int i = h[t]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dist[j] > dist[t] + w[i])
//            {
//                dist[j] = dist[t] + w[i];
//                cnt[j] = cnt[t] + 1;
//                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
//                if (!st[j])
//                {
//                    q.push(j);
//                    st[j] = true;
//                }
//            }
//        }
//    }
//
//    return false;
//}

// floyd求最短路
//初始化：
//for (int i = 1; i <= n; i++)
//for (int j = 1; j <= n; j++)
//if (i == j) d[i][j] = 0;
//else d[i][j] = INF;
//
//// 算法结束后，d[a][b]表示a到b的最短距离
//void floyd()
//{
//    for (int k = 1; k <= n; k++)
//        for (int i = 1; i <= n; i++)
//            for (int j = 1; j <= n; j++)
//                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
//}

// prim求最小生成树
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 510, INF = 0x3f3f3f3f;
//
//int n, m;
//int g[N][N], dist[N];
//bool st[N];
//
//int prim()
//{
//    memset(dist, 0x3f, sizeof dist);
//
//    int res = 0;
//    dist[1] = 0;
//
//    for (int i = 0; i < n; i++)
//    {
//        int t = -1;
//
//        for (int j = 1; j <= n; j++)
//            if (!st[j] && (t == -1 || dist[t] > dist[j]))
//                t = j;
//
//        if (dist[t] == INF) return INF;
//
//        res += dist[t];
//        st[t] = true;
//
//        for (int j = 1; j <= n; j++)
//            dist[j] = min(dist[j], g[t][j]);
//
//    }
//
//    return res;
//}
//
//int main()
//{
//    cin >> n >> m;
//
//    memset(g, 0x3f, sizeof g);
//
//    while (m--)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        g[a][b] = g[b][a] = min(g[a][b], c);
//    }
//
//    int t = prim();
//
//    if (t == INF) puts("impossible");
//    else cout << t << endl;
//
//    return 0;
//}

// kruskal求最小生成树
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 100010, M = 2 * N;
//const int INF = 0x3f3f3f3f;
//int p[N];
//int n, m;
//
//struct Edge     // 存储边
//{
//    int a, b, w;
//
//    bool operator<(const Edge& W) const
//    {
//        return w < W.w;
//    }
//}edges[M];
//
//int find(int x)
//{
//    if (p[x] != x) p[x] = find(p[x]);
//    return p[x];
//}
//
//int kruskal()
//{
//    sort(edges, edges + m);
//
//    for (int i = 1; i <= n; i++) p[i] = i;
//
//    int res = 0, cnt = 0;
//    for (int i = 0; i < m; i++)
//    {
//        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
//
//        a = find(a), b = find(b);
//        if (a != b)
//        {
//            p[a] = b;
//            res += w;
//            cnt++;
//        }
//    }
//
//    if (cnt < n - 1) return INF;
//    return res;
//}
//
//int main()
//{
//    cin >> n >> m;
//
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, w;
//        cin >> a >> b >> w;
//        edges[i] = { a, b, w };
//    }
//
//    int t = kruskal();
//
//    if (t == INF) puts("impossible");
//    else cout << t << endl;
//
//    return 0;
//}

// 染色法判断二分图
//#include <iostream>
//#include <cstring>
//#include <algorithm>
// 
//using namespace std;
//
//const int N = 100010, M = 2 * N;
//int h[N], e[M], ne[M], idx;
//int n, m;
//int color[N];
//
//void add(int a, int b)
//{
//    e[idx] = b;
//    ne[idx] = h[a];
//    h[a] = idx;
//    idx++;
//}
//
//bool dfs(int u, int c)
//{
//    color[u] = c;
//    for (int i = h[u]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        if (color[j] == -1)
//        {
//            if (!dfs(j, !c)) return false;
//        }
//        else if (color[j] == c) return false;
//    }
//    return true;
//}
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//
//    memset(h, -1, sizeof h);
//    memset(color, -1, sizeof color);
//
//    while (m--)
//    {
//        int a, b;
//        scanf("%d %d", &a, &b);
//        add(a, b); add(b, a);
//    }
//
//    bool flag = true;
//    for (int i = 1; i <= n; i++)
//    {
//        if (color[i] == -1)
//        {
//            if (!dfs(i, 0))
//            {
//                flag = false;
//                break;
//            }
//        }
//    }
//
//    if (flag) puts("Yes");
//    else puts("No");
//
//    return 0;
//}

// 匈牙利算法
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 510, M = 100010;
//
//int n1, n2, m;
//int h[N], e[M], ne[M], idx;
//int match[N];
//bool st[N];
//
//void add(int a, int b)
//{
//    e[idx] = b;
//    ne[idx] = h[a];
//    h[a] = idx;
//    idx++;
//}
//
//bool find(int x)
//{
//    for (int i = h[x]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        if (!st[j])
//        {
//            st[j] = true;
//            if (match[j] == 0 || find(match[j]))
//            {
//                match[j] = x;
//                return true;
//            }
//        }
//    }
//    return false;
//}
//
//int main()
//{
//    scanf("%d%d%d", &n1, &n2, &m);
//
//    memset(h, -1, sizeof h);
//
//    while (m--)
//    {
//        int a, b;
//        scanf("%d%d", &a, &b);
//        add(a, b);
//    }
//
//    int res = 0;
//    for (int i = 1; i <= n1; i++)
//    {
//        memset(st, false, sizeof st);
//        if (find(i)) res++;
//    }
//
//    printf("%d\n", res);
//
//    return 0;
//}

// 区间选点
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 100010;
//
//struct Range
//{
//    int l, r;
//    bool operator<(const Range& w) const
//    {
//        return r < w.r;
//    }
//}range[N];
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    for (int i = 0; i < n; i++)
//    {
//        int l, r;
//        scanf("%d %d", &l, &r);
//        range[i] = { l, r };
//    }
//
//    sort(range, range + n);
//
//    int res = 0, ed = -2e9;
//    for (int i = 0; i < n; i++)
//    {
//        if (range[i].l > ed)
//        {
//            res++;
//            ed = range[i].r;
//        }
//    }
//
//    printf("%d\n", res);
//
//    return 0;
//}

// 区间分组
//#include <iostream>
//using namespace std;
//
//#include <queue>
//#include <cstring>
//#include <algorithm>
//
//const int N = 100010;
//
//struct Range
//{
//    int l, r;
//    bool operator<(const Range& w) const
//    {
//        return l < w.l;
//    }
//}range[N];
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    for (int i = 0; i < n; i++)
//    {
//        int l, r;
//        scanf("%d %d", &l, &r);
//        range[i] = { l, r };
//    }
//
//    sort(range, range + n);
//
//    priority_queue<int, vector<int>, greater<int>> heap;
//
//    for (int i = 0; i < n; i++)
//    {
//        auto t = range[i];
//
//        if (heap.empty() || heap.top() >= t.l) heap.push(t.r);
//        else
//        {
//            heap.pop();
//            heap.push(t.r);
//        }
//    }
//
//    printf("%d\n", heap.size());
//
//    return 0;
//}

// 区间覆盖
//#include <iostream>
//#include <algorithm>
//#include <cstring>
//
//using namespace std;
//
//const int N = 100010;
//
//// 定义表示区间的结构体
//struct Range
//{
//    int l, r;
//    bool operator<(const Range& w) const
//    {
//        return l < w.l;
//    }
//}range[N];
//
//int main()
//{
//    int s, t;
//    scanf("%d %d", &s, &t);
//
//    int n;
//    scanf("%d", &n);
//
//    for (int i = 0; i < n; i++)
//    {
//        int l, r;
//        scanf("%d %d", &l, &r);
//        range[i] = { l, r };
//    }
//
//
//    sort(range, range + n);
//
//    int res = 0;
//    bool success = false;
//
//    for (int i = 0; i < n; )
//    {
//        int j = i, r = -2e9;
//
//        while (j < n && range[j].l <= s)
//        {
//            r = max(r, range[j].r);
//            j++;
//        }
//
//        if (r < s)
//        {
//            res = -1;
//            break;
//        }
//
//        res++;
//
//        if (r >= t)
//        {
//            success = true;
//            break;
//        }
//
//        s = r;
//        i = j;
//    }
//
//    if (success)
//        printf("%d\n", res);
//    else
//        printf("-1\n");
//
//    return 0;
//}

// Huffman树
//#include <iostream>
//using namespace std;
//
//#include <queue>
//#include <cstring>
//#include <algorithm>
//
//const int N = 10010;
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    priority_queue<int, vector<int>, greater<int>> heap;
//
//    for (int i = 0; i < n; i++)
//    {
//        int a;
//        scanf("%d", &a);
//        heap.push(a);
//    }
//
//    int res = 0;
//    while (heap.size() > 1)
//    {
//        int t1 = heap.top();
//        heap.pop();
//
//        int t2 = heap.top();
//        heap.pop();
//
//        res += t1 + t2;
//        heap.push(t1 + t2);
//    }
//
//    printf("%d\n", res);
//
//    return 0;
//}

// 推公式
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 50010;
//
//struct Cow
//{
//    int w, s;
//    bool operator<(const Cow& c) const
//    {
//        return (w + s) < (c.w + c.s);
//    }
//}cow[N];
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    for (int i = 1; i <= n; i++)
//        scanf("%d %d", &cow[i].w, &cow[i].s);
//
//    sort(cow + 1, cow + 1 + n);
//
//    for (int i = 0; i < n; i++)
//        cow[i].w += cow[i - 1].w;
//
//    int res = -2e9;
//    for (int i = 1; i <= n; i++)
//        res = max(res, cow[i - 1].w - cow[i].s);
//
//    printf("%d\n", res);
//
//
//    return 0;
//}

// 递推法求组合数
// c[a][b] 表示从a个苹果中选b个的方案数
//for (int i = 0; i < N; i++)
//    for (int j = 0; j <= i; j++)
//        if (!j) c[i][j] = 1;
//        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

// 计数dp
//1. num[i] < x, 0
//2. num[i] == x, 0 ~ efg
//3. num[i] > x, 0 ~ 999
//
//#include <iostream>
//#include <algorithm>
//#include <vector>
//using namespace std;
//
//const int N = 10;
//
//int get(vector<int> num, int l, int r)
//{
//    int res = 0;
//    for (int i = l; i >= r; i--) res = res * 10 + num[i];
//    return res;
//}
//
//int power10(int x)
//{
//    int res = 1;
//    while (x--) res *= 10;
//    return res;
//}
//
//int count(int n, int x)
//{
//    if (!n) return 0;
//
//    vector<int> num;
// 
//    while (n)
//    {
//        num.push_back(n % 10);
//        n /= 10;
//    }
// 
//    n = num.size();
// 
//1. num[i] < x, 0
//2. num[i] == x, 0 ~ efg
//3. num[i] > x, 0 ~ 999
//
//    int res = 0;
//    for (int i = n - 1 - !x; i >= 0; i--)
//    {
//        if (i < n - 1)
//        {
//            res += get(num, n - 1, i + 1) * power10(i);
//            if (!x) res -= power10(i);
//        }
//
//        if (num[i] == x) res += get(num, i - 1, 0) + 1;
//        else if (num[i] > x) res += power10(i);
//    }
//
//    return res;
//}
//
//int main()
//{
//    int a, b;
//    while (cin >> a >> b, a)
//    {
//        if (a > b) swap(a, b);
//
//        for (int i = 0; i <= 9; i++)
//            cout << count(b, i) - count(a - 1, i) << ' ';
//        cout << endl;
//    }
//
//    return 0;
//}

// 通过预处理逆元的方式求组合数
// 首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
// 如果取模的数是质数，可以用费马小定理求逆元
//int qmi(int a, int k, int p)    // 快速幂模板
//{
//    int res = 1;
//    while (k)
//    {
//        if (k & 1) res = (LL)res * a % p;
//        a = (LL)a * a % p;
//        k >>= 1;
//    }
//    return res;
//}
//
//// 预处理阶乘的余数和阶乘逆元的余数
//fact[0] = infact[0] = 1;
//for (int i = 1; i < N; i++)
//{
//    fact[i] = (LL)fact[i - 1] * i % mod;
//    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
//}

// Lucas定理
//若p是质数，则对于任意整数 1 <= m <= n，有：
//C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
//
//int qmi(int a, int k, int p)  // 快速幂模板
//{
//    int res = 1 % p;
//    while (k)
//    {
//        if (k & 1) res = (LL)res * a % p;
//        a = (LL)a * a % p;
//        k >>= 1;
//    }
//    return res;
//}
//
//int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
//{
//    if (a < b) return 0;
//
//    LL x = 1, y = 1;  // x是分子，y是分母
//    for (int i = a, j = 1; j <= b; i--, j++)
//    {
//        x = (LL)x * i % p;
//        y = (LL)y * j % p;
//    }
//
//    return x * (LL)qmi(y, p - 2, p) % p;
//}
//
//int lucas(LL a, LL b, int p)
//{
//    if (a < p && b < p) return C(a, b, p);
//    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
//}

// 状态压缩dp
// 最短Hamilton路径
//// 1.哪些点被用过；
//// 2.目前停在哪个点上
//// 2^20 * 20 = 2 * 10^7
//// f[state][j] = f[state_k][k] + weight[k][j], state_k = 除掉 j 之后的集合，state_k 要包含 k
// 
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 20, M = 1 << 20;
//int f[M][N], w[N][N];
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n; j++)
//            scanf("%d", &w[i][j]);
//
//    memset(f, 0x3f, sizeof f);
//    f[1][0] = 0;
//
//    for (int i = 0; i < 1 << n; i++)
//        for (int j = 0; j < n; j++)
//            if (i >> j & 1)
//                for (int k = 0; k < n; k++)
//                    if (i - (1 << j) >> k & 1)
//                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
//
//    cout << f[(1 << n) - 1][n - 1] << endl;
//
//    return 0;
//}

// 记忆化搜索
//#include <iostream>
//using namespace std;
//
//#include <cstring>
//#include <algorithm>
//
//const int N = 310;
//int n, m;
//int h[N][N];
//int f[N][N];
//
//int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
//int dp(int x, int y)
//{
//    int& v = f[x][y];
//    if (v != -1) return v;
//
//    v = 1;
//
//    for (int i = 0; i < 4; i++)
//    {
//        int a = x + dx[i], b = y + dy[i];
//        if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
//            v = max(v, dp(a, b) + 1);
//    }
//
//    return v;
//}
//
//int main()
//{
//    scanf("%d %d", &n, &m);
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            scanf("%d", &h[i][j]);
//        }
//    }
//
//    memset(f, -1, sizeof f);
//
//    int res = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            res = max(res, dp(i, j));
//        }
//    }
//
//    printf("%d\n", res);
//
//    return 0;
//}

// 树形dp
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 6010;
//
//int n;
//int h[N], e[N], ne[N], idx;
//int happy[N];
//int f[N][2];
//bool has_fa[N];
//
//void add(int a, int b)
//{
//    e[idx] = b;
//    ne[idx] = h[a];
//    h[a] = idx;
//    idx++;
//}
//
//void dfs(int u)
//{
//    f[u][1] = happy[u];
//
//    for (int i = h[u]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        dfs(j);
//
//        f[u][1] += f[j][0];
//        f[u][0] += max(f[j][0], f[j][1]);
//    }
//}
//
//int main()
//{
//    scanf("%d", &n);
//
//    for (int i = 1; i <= n; i++) scanf("%d", &happy[i]);
//
//    memset(h, -1, sizeof h);
//
//    for (int i = 0; i < n - 1; i++)
//    {
//        int a, b;
//        scanf("%d%d", &a, &b);
//        add(b, a);
//        has_fa[a] = true;
//    }
//
//    int root = 1;
//    while (has_fa[root]) root++;
//
//    dfs(root);
//
//    printf("%d\n", max(f[root][0], f[root][1]));
//
//    return 0;
//}

// 状态压缩dp:蒙德里安的梦想
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 12, M = 1 << N;
//
//int n, m;
//long long f[N][M];
//bool st[M];
//
//int main()
//{
//    while (cin >> n >> m, n || m)
//    {
//        for (int i = 0; i < 1 << n; i++)
//        {
//            int cnt = 0;
//            st[i] = true;
//            for (int j = 0; j < n; j++)
//                if (i >> j & 1)
//                {
//                    if (cnt & 1) st[i] = false;
//                    cnt = 0;
//                }
//                else cnt++;
//            if (cnt & 1) st[i] = false;
//        }
//
//        memset(f, 0, sizeof f);
//        f[0][0] = 1;
//        for (int i = 1; i <= m; i++)
//            for (int j = 0; j < 1 << n; j++)
//                for (int k = 0; k < 1 << n; k++)
//                    if ((j & k) == 0 && st[j | k])
//                        f[i][j] += f[i - 1][k];
//
//        cout << f[m][0] << endl;
//    }
//    return 0;
//}

// 扩展欧几里得算法
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//int exgcd(int a, int b, int& x, int& y)
//{
//    if (!b)
//    {
//        x = 1, y = 0;
//        return a;
//    }
//    int d = exgcd(b, a % b, y, x);
//    y -= a / b * x;
//    return d;
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    while (n--)
//    {
//        int a, b;
//        scanf("%d%d", &a, &b);
//        int x, y;
//        exgcd(a, b, x, y);
//        printf("%d %d\n", x, y);
//    }
//
//    return 0;
//}

// 线性同余方程
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//typedef long long LL;
//
//
//int exgcd(int a, int b, int& x, int& y)
//{
//    if (!b)
//    {
//        x = 1, y = 0;
//        return a;
//    }
//    int d = exgcd(b, a % b, y, x);
//    y -= a / b * x;
//    return d;
//}
//
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int a, b, m;
//        scanf("%d%d%d", &a, &b, &m);
//
//        int x, y;
//        int d = exgcd(a, m, x, y);
//        if (b % d) puts("impossible");
//        else printf("%d\n", (LL)b / d * x % m);
//    }
//
//    return 0;
//}

// 中国剩余定理
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//typedef long long LL;
//
//
//LL exgcd(LL a, LL b, LL& x, LL& y)
//{
//    if (!b)
//    {
//        x = 1, y = 0;
//        return a;
//    }
//
//    LL d = exgcd(b, a % b, y, x);
//    y -= a / b * x;
//    return d;
//}
//
//
//int main()
//{
//    int n;
//    cin >> n;
//
//    LL x = 0, m1, a1;
//    cin >> m1 >> a1;
//    for (int i = 0; i < n - 1; i++)
//    {
//        LL m2, a2;
//        cin >> m2 >> a2;
//        LL k1, k2;
//        LL d = exgcd(m1, m2, k1, k2);
//        if ((a2 - a1) % d)
//        {
//            x = -1;
//            break;
//        }
//
//        k1 *= (a2 - a1) / d;
//        k1 = (k1 % (m2 / d) + m2 / d) % (m2 / d);
//
//        x = k1 * m1 + a1;
//
//        LL m = abs(m1 / d * m2);
//        a1 = k1 * m1 + a1;
//        m1 = m;
//    }
//
//    if (x != -1) x = (a1 % m1 + m1) % m1;
//
//    cout << x << endl;
//
//    return 0;
//}

// 高斯消元解线性方程组
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <cmath>
//
//using namespace std;
//
//const int N = 110;
//const double eps = 1e-8;
//
//int n;
//double a[N][N];
//
//int gauss()  // 高斯消元，答案存于a[i][n]中，0 <= i < n
//{
//    int c, r;
//    for (c = 0, r = 0; c < n; c++)
//    {
//        int t = r;
//        for (int i = r; i < n; i++)  // 找绝对值最大的行
//            if (fabs(a[i][c]) > fabs(a[t][c]))
//                t = i;
//
//        if (fabs(a[t][c]) < eps) continue;
//
//        for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);  // 将绝对值最大的行换到最顶端
//        for (int i = n; i >= c; i--) a[r][i] /= a[r][c];  // 将当前行的首位变成1
//        for (int i = r + 1; i < n; i++)  // 用当前行将下面所有的列消成0
//            if (fabs(a[i][c]) > eps)
//                for (int j = n; j >= c; j--)
//                    a[i][j] -= a[r][j] * a[i][c];
//
//        r++;
//    }
//
//    if (r < n)
//    {
//        for (int i = r; i < n; i++)
//            if (fabs(a[i][n]) > eps)
//                return 2; // 无解
//        return 1; // 有无穷多组解
//    }
//
//    for (int i = n - 1; i >= 0; i--)
//        for (int j = i + 1; j < n; j++)
//            a[i][n] -= a[i][j] * a[j][n];
//
//    return 0; // 有唯一解
//}
//
//
//int main()
//{
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n + 1; j++)
//            scanf("%lf", &a[i][j]);
//
//    int t = gauss();
//    if (t == 2) puts("No solution");
//    else if (t == 1) puts("Infinite group solutions");
//    else
//    {
//        for (int i = 0; i < n; i++)
//            printf("%.2lf\n", a[i][n]);
//    }
//
//    return 0;
//}

// 高斯消元解异或线性方程组
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 110;
//
//
//int n;
//int a[N][N];
//
//
//int gauss()
//{
//    int c, r;
//    for (c = 0, r = 0; c < n; c++)
//    {
//        int t = r;
//        for (int i = r; i < n; i++)
//            if (a[i][c])
//                t = i;
//
//        if (!a[t][c]) continue;
//
//        for (int i = c; i <= n; i++) swap(a[r][i], a[t][i]);
//        for (int i = r + 1; i < n; i++)
//            if (a[i][c])
//                for (int j = n; j >= c; j--)
//                    a[i][j] ^= a[r][j];
//
//        r++;
//    }
//
//    if (r < n)
//    {
//        for (int i = r; i < n; i++)
//            if (a[i][n])
//                return 2;
//        return 1;
//    }
//
//    for (int i = n - 1; i >= 0; i--)
//        for (int j = i + 1; j < n; j++)
//            a[i][n] ^= a[i][j] * a[j][n];
//
//    return 0;
//}
//
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n + 1; j++)
//            cin >> a[i][j];
//
//    int t = gauss();
//
//    if (t == 0)
//    {
//        for (int i = 0; i < n; i++) cout << a[i][n] << endl;
//    }
//    else if (t == 1) puts("Multiple sets of solutions");
//    else puts("No solution");
//
//    return 0;
//}

// 分解质因数法求组合数
//#include <iostream>
//#include <algorithm>
//#include <vector>
//
//using namespace std;
//
//
//const int N = 5010;
//
//int primes[N], cnt;
//int sum[N];
//bool st[N];
//
//
//void get_primes(int n)
//{
//    for (int i = 2; i <= n; i++)
//    {
//        if (!st[i]) primes[cnt++] = i;
//        for (int j = 0; primes[j] <= n / i; j++)
//        {
//            st[primes[j] * i] = true;
//            if (i % primes[j] == 0) break;
//        }
//    }
//}
//
//
//int get(int n, int p)
//{
//    int res = 0;
//    while (n)
//    {
//        res += n / p;
//        n /= p;
//    }
//    return res;
//}
//
//
//vector<int> mul(vector<int> a, int b)
//{
//    vector<int> c;
//    int t = 0;
//    for (int i = 0; i < a.size(); i++)
//    {
//        t += a[i] * b;
//        c.push_back(t % 10);
//        t /= 10;
//    }
//    while (t)
//    {
//        c.push_back(t % 10);
//        t /= 10;
//    }
//    return c;
//}
//
//
//int main()
//{
//    int a, b;
//    cin >> a >> b;
//
//    get_primes(a);
//
//    for (int i = 0; i < cnt; i++)
//    {
//        int p = primes[i];
//        sum[i] = get(a, p) - get(a - b, p) - get(b, p);
//    }
//
//    vector<int> res;
//    res.push_back(1);
//
//    for (int i = 0; i < cnt; i++)
//        for (int j = 0; j < sum[i]; j++)
//            res = mul(res, primes[i]);
//
//    for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
//    puts("");
//
//    return 0;
//}

// 给定n个0和n个1，它们按照某种顺序排成长度为2n的序列
// 满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//typedef long long LL;
//
//const int N = 100010, mod = 1e9 + 7;
//
//
//int qmi(int a, int k, int p)
//{
//    int res = 1;
//    while (k)
//    {
//        if (k & 1) res = (LL)res * a % p;
//        a = (LL)a * a % p;
//        k >>= 1;
//    }
//    return res;
//}
//
//
//int main()
//{
//    int n;
//    cin >> n;
//
//    int a = n * 2, b = n;
//    int res = 1;
//    for (int i = a; i > a - b; i--) res = (LL)res * i % mod;
//
//    for (int i = 1; i <= b; i++) res = (LL)res * qmi(i, mod - 2, mod) % mod;
//
//    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
//
//    cout << res << endl;
//
//    return 0;
//}

// 容斥原理
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//typedef long long LL;
//
//const int N = 20;
//
//int p[N];
//
//
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//
//    for (int i = 0; i < m; i++) cin >> p[i];
//
//    int res = 0;
//    for (int i = 1; i < 1 << m; i++)
//    {
//        int t = 1, s = 0;
//        for (int j = 0; j < m; j++)
//            if (i >> j & 1)
//            {
//                if ((LL)t * p[j] > n)
//                {
//                    t = -1;
//                    break;
//                }
//                t *= p[j];
//                s++;
//            }
//
//        if (t != -1)
//        {
//            if (s % 2) res += n / t;
//            else res -= n / t;
//        }
//    }
//
//    cout << res << endl;
//
//    return 0;
//}

// Nim游戏
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 100010;
//
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    int res = 0;
//    while (n--)
//    {
//        int x;
//        scanf("%d", &x);
//        res ^= x;
//    }
//
//    if (res) puts("Yes");
//    else puts("No");
//
//    return 0;
//}

// 台阶-Nim游戏
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 100010;
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//
//    int res = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int x;
//        scanf("%d", &x);
//        if (i & 1) res ^= x;
//    }
//
//    if (res) puts("Yes");
//    else puts("No");
//
//    return 0;
//}

// 集合-Nim游戏
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//#include <unordered_set>
//
//using namespace std;
//
//const int N = 110, M = 10010;
//
//int n, m;
//int s[N], f[M];
//
//
//int sg(int x)
//{
//    if (f[x] != -1) return f[x];
//
//    unordered_set<int> S;
//    for (int i = 0; i < m; i++)
//    {
//        int sum = s[i];
//        if (x >= sum) S.insert(sg(x - sum));
//    }
//
//    for (int i = 0; ; i++)
//        if (!S.count(i))
//            return f[x] = i;
//}
//
//
//int main()
//{
//    cin >> m;
//    for (int i = 0; i < m; i++) cin >> s[i];
//    cin >> n;
//
//    memset(f, -1, sizeof f);
//
//    int res = 0;
//    for (int i = 0; i < n; i++)
//    {
//        int x;
//        cin >> x;
//        res ^= sg(x);
//    }
//
//    if (res) puts("Yes");
//    else puts("No");
//
//    return 0;
//}

// 拆分-Nim游戏
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//#include <unordered_set>
//
//using namespace std;
//
//const int N = 110;
//
//
//int n;
//int f[N];
//
//
//int sg(int x)
//{
//    if (f[x] != -1) return f[x];
//
//    unordered_set<int> S;
//    for (int i = 0; i < x; i++)
//        for (int j = 0; j <= i; j++)
//            S.insert(sg(i) ^ sg(j));
//
//    for (int i = 0;; i++)
//        if (!S.count(i))
//            return f[x] = i;
//}
//
//
//int main()
//{
//    cin >> n;
//
//    memset(f, -1, sizeof f);
//
//    int res = 0;
//    while (n--)
//    {
//        int x;
//        cin >> x;
//        res ^= sg(x);
//    }
//
//    if (res) puts("Yes");
//    else puts("No");
//
//    return 0;
//}

//// 动态规划：摘花生
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 110;
//
//int n, m;
//int w[N][N];
//int f[N][N];
//
//int main()
//{
//    int T;
//    scanf("%d", &T);
//    while (T--)
//    {
//        scanf("%d%d", &n, &m);
//        for (int i = 1; i <= n; i++)
//            for (int j = 1; j <= m; j++)
//                scanf("%d", &w[i][j]);
//
//        for (int i = 1; i <= n; i++)
//            for (int j = 1; j <= m; j++)
//                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
//
//        printf("%d\n", f[n][m]);
//    }
//
//    return 0;
//}